package com.leo.m1803.d06;

/**
 * Created by LEO on 2018/3/6.
 */
public class Offer06 {
    static class Node{
        int val;
        Node left,right;
        public Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static Node g(int[] pre, int[] in){
        return g1(pre, 0, in, 0, in.length-1);
    }

    private static Node g1(int[] pre, int ps, int[] in, int is, int ie){
        if (is<=ie && ps<pre.length){
            int root = pre[ps];
            Node node = new Node(root, null, null);
            int pos=is;
            for (int i = is; i <= ie ; i++) {
                if (in[i] == root){ pos=i; break; }
            }
            node.left = g1(pre, ps+1, in, is, pos-1);
            node.right = g1(pre, ps+pos-is+1, in, pos+1, ie);
            return node;
        }
        return null;
    }
}
